#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int searchInsert(int* nums, int numsSize, int target){
    int mix = 0,max = numsSize - 1;
    while (mix != max)
    {
        int mid = (max + mix) >> 1;
        if (nums[mid] < target)
            mix = mid + 1;
        else if (nums[mid] > target)
            max = mid;
        else
            return mid;
    }
    return nums[max]<target ? max+1 : max;
}

int main(void)
{
    int nums[] = {1,3,5,6},numsSize = 4, target = 9;
    int result = searchInsert(nums,numsSize,target);
    printf("%d\n",result);

    return 0;
}